package com.conjane.algo.array_list;

import java.util.BitSet;

/**
 * 从有序数组中查找缺少的数值
 */
public class MissNumberInArray {

    /**
     * 根据总数值的和减去现有数组的和，得到缺少的数据，适合缺少一个数值的场景
     * @param array
     * @param totalCount
     * @return
     */
    public static int getMissingNumber(int[] array,int totalCount){
        int totalSum = (1 + totalCount) * totalCount / 2;
        int sum = 0;
        for (int i : array) {
            sum = sum + i;
        }
        return totalSum - sum;
    }

    /**
     * 利用位图，计算缺少的数值，适合多个数值缺少的场景
     * @param array
     * @param totalCount
     */
    public static void printMissingNumber(int[] array,int totalCount){
        int missingCount = totalCount - array.length;
        BitSet bitSet = new BitSet();
        for (int i : array) {
            bitSet.set(i - 1);
        }
        for (int i = 0; i < missingCount; i++) {
            int missNumber = bitSet.nextClearBit(i);
            System.out.println(++missNumber);
        }
    }

    public static void main(String[] args) {
        int[] array = new int[]{1,2,3,4,5,7,8,9,10};
        printMissingNumber(array,10);
        System.out.println(getMissingNumber(array,10));
    }
}
